<!DOCTYPE html>
<html lang="zh-CH" >
<head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <meta name="author" content="" />
	
	
	
	<title>读书笔记之算法 ｜ zansimple</title>
	
    
    
    <meta name="description" content="算法与算法描述 算法： 定义:算法是规则的有限集合，是为解决特定问题而规定的一系列操作。
特性:  有限性:有限步骤之内正常结束，不能形成无穷循环。 确定性: 算法中的每一个步骤必须有确定的含义，无二义。 输入: 有多个或0个输入。 输出: 至少有一个或多个输出。 可行性: 原则上能精确的进行操作通过已实现的基本运算执行有限次而完成。  设计的要求  算法的正确性 可读性 健壮性 高效和低耗  算法描述  描述工具：自然语言，框图，高级语言。 程序：是算法在计算机上的实现
自然语言简单但有二义
框图易表达处理流程，难表达数据流程
高级语言准确但细节过多  类语言 类语言接近于高级语言而又不是严格的高级语言，具有高级语言的一般规格，撇掉语言中的细节。把注意力主要集中在算法处理步骤的本身上。
要点  掌握算法的定义和特性 力争做出解决一类问题的优秀算法 算法描述用类语言，突出处理过程思路  算法性能评价 标准：算法执行占用机器资源主要表现在执行时间和存储空间两个方面。
性能评价：算法效率与问题规模N有关，应是问题规模的函数。
问题规模N：反映问题大小的本质数且对于不同的问题其含义不同
 对矩阵是阶数 对多项式运算是多项式项数 对图是定点个数 对集合运算是集合中的元素个数  有关数量关系的计算 数量关系评价可以提现在时间和空间上
关于算法的执行时间  算法执行时间 = 其所有语句执行时间的总和 语句执行时间 = 该条语句的执行次数 * 执行一次所需时间  分析 算法实际执行时间与机器硬件和系统软件等多种因素有关，算法时间比较的本质是算法中语句执行次数的比较，相当于语句执行一次的时间均为 &amp;lsquo;1&amp;rsquo; 不起作用。
语句频度 语句频度：是指该语句在一个算法中重复执行的次数
例：两个 n*n矩阵相乘对应的语句频度 算法语句 n for(i=0;i&amp;lt;n;i&#43;&#43;)n^2 for(j=0;j&amp;lt;n;j&#43;&#43;){n^2 c[i][j] = 0;n^3 for(k=0;k&amp;lt;n;k&#43;&#43;)n^3 c[i][j] = c[i][j]&#43; a[i][k]*b[k][j];} 总执行次数 f(n) = 2n^3 &#43; 2n^2 &#43; n" />
    

    

	
    
    <link rel="shortcut icon" href="https://lenzan.github.io/images/favicon.ico" />

    <link rel="stylesheet" type="text/css" media="screen" href="https://lenzan.github.io/css/normalize.css" />
    <link rel="stylesheet" type="text/css" media="screen" href="https://cdn.jsdelivr.net/npm/animate.css@4.1.0/animate.min.css" />
    <link rel="stylesheet" type="text/css" media="screen" href="https://lenzan.github.io/css/zozo.css" />
	<link rel="stylesheet" type="text/css" media="screen" href="https://cdn.jsdelivr.net/npm/remixicon@2.5.0/fonts/remixicon.css" />
    <link rel="stylesheet" type="text/css" media="screen" href="https://lenzan.github.io/css/highlight.css" />

    
    
</head>

<body>
    <div class="main animate__animated animate__fadeInDown">
        <div class="nav_container animated fadeInDown">
    <div class="site_nav" id="site_nav">
        <ul>
            
            <li>
                <a href="/">首页</a>
            </li>
            
            <li>
                <a href="/">unity</a>
            </li>
            
            <li>
                <a href="/">归档</a>
            </li>
            
            <li>
                <a href="/">关于</a>
            </li>
            
        </ul>
    </div>
    <div class="menu_icon">
        <a id="menu_icon"><i class="ri-menu-line"></i></a>
    </div>
</div>
        <div class="header animated fadeInDown">
    <div class="site_title_container">
        <div class="site_title">
            <h1>
                <a href="https://lenzan.github.io/">
                    <span>zansimple</span>
                    <img src="https://lenzan.github.io/images/logo.svg" />
                </a>
            </h1>
        </div>
        <div class="description">
            <p class="sub_title">专注于Unity虚拟现实开发，游戏开发</p>
            <div class="my_socials">
                
                <a href="https://lenzan.github.io/index.xml" type="application/rss+xml" title="rss" target="_blank"><i
                        class="ri-rss-fill"></i></a>
            </div>
        </div>
    </div>
</div>
        <div class="content">
            <div class="post_page">
                <div class="post animate__animated animate__fadeInDown">
                    <div class="post_title post_detail_title">
                        <h2><a href='/posts/data/data-structure-2/'>读书笔记之算法</a></h2>
                        <span class="date">2018.06.20</span>
                    </div>
                    <div class="post_content markdown"><h2 id="算法与算法描述">算法与算法描述</h2>
<h3 id="算法">算法：</h3>
<p>定义:算法是规则的有限集合，是为解决特定问题而规定的一系列操作。</p>
<h3 id="特性">特性:</h3>
<ul>
<li>有限性:有限步骤之内正常结束，不能形成无穷循环。</li>
<li>确定性: 算法中的每一个步骤必须有确定的含义，无二义。</li>
<li>输入: 有多个或0个输入。</li>
<li>输出: 至少有一个或多个输出。</li>
<li>可行性: 原则上能精确的进行操作通过已实现的基本运算执行有限次而完成。</li>
</ul>
<h3 id="设计的要求">设计的要求</h3>
<ul>
<li>算法的正确性</li>
<li>可读性</li>
<li>健壮性</li>
<li>高效和低耗</li>
</ul>
<h3 id="算法描述">算法描述</h3>
<ul>
<li>描述工具：自然语言，框图，高级语言。</li>
<li>程序：是算法在计算机上的实现<br>
自然语言简单但有二义<br>
框图易表达处理流程，难表达数据流程<br>
高级语言准确但细节过多</li>
</ul>
<h4 id="类语言">类语言</h4>
<p>类语言接近于高级语言而又不是严格的高级语言，具有高级语言的一般规格，撇掉语言中的细节。把注意力主要集中在算法处理步骤的本身上。</p>
<h3 id="要点">要点</h3>
<ul>
<li>掌握算法的定义和特性</li>
<li>力争做出解决一类问题的优秀算法</li>
<li>算法描述用类语言，突出处理过程思路</li>
</ul>
<h2 id="算法性能评价">算法性能评价</h2>
<p>标准：算法执行占用机器资源主要表现在执行时间和存储空间两个方面。<br>
性能评价：算法效率与问题规模N有关，应是问题规模的函数。<br>
问题规模N：反映问题大小的本质数且对于不同的问题其含义不同</p>
<ul>
<li>对矩阵是阶数</li>
<li>对多项式运算是多项式项数</li>
<li>对图是定点个数</li>
<li>对集合运算是集合中的元素个数</li>
</ul>
<h3 id="有关数量关系的计算">有关数量关系的计算</h3>
<p>数量关系评价可以提现在时间和空间上</p>
<h3 id="关于算法的执行时间">关于算法的执行时间</h3>
<ul>
<li>算法执行时间 = 其所有语句执行时间的总和</li>
<li>语句执行时间 = 该条语句的执行次数 * 执行一次所需时间</li>
</ul>
<h3 id="分析">分析</h3>
<p>算法实际执行时间与机器硬件和系统软件等多种因素有关，算法时间比较的本质是算法中语句执行次数的比较，相当于语句执行一次的时间均为 &lsquo;1&rsquo; 不起作用。</p>
<h3 id="语句频度">语句频度</h3>
<p>语句频度：是指该语句在一个算法中重复执行的次数</p>
<pre><code>例：两个 n*n矩阵相乘
对应的语句频度                  算法语句            
  n          for(i=0;i&lt;n;i++)
  n^2           for(j=0;j&lt;n;j++)
                    {
  n^2                  c[i][j] = 0;
  n^3                  for(k=0;k&lt;n;k++)
  n^3                       c[i][j] = c[i][j]+ a[i][k]*b[k][j];

                    }
</code></pre>
<p>总执行次数 f(n) = 2n^3 + 2n^2 + n</p>
<h3 id="算法的时间复杂度">算法的时间复杂度</h3>
<p>从语句频度刻画随问题规模 n 增加的函数 f(n) 执行时间量度。<br>
记作 T(n) = O(f(n))<br>
例：给出 x=x+1 的使劲按复杂度分析</p>
<ol>
<li>x=x+1 ; 时间复杂度为O(1) ，称为常数阶。</li>
<li>for(i=1;i&lt;n;i++) x=x+1; 时间复杂度为O(n)， 称为线性阶。</li>
<li>for(i=1;i&lt;n;i++){for(j=1;j&lt;n;j++){x = x + 1;}} 时间复杂度为O(n^2)，称为平方阶。</li>
</ol>
<h3 id="最坏时间复杂度">最坏时间复杂度</h3>
<p>定义：算法在最坏的情况下基本操作执行时间的上界。</p>
<p>基本算法：是指算法中所研究问题的基本运算操作</p>
<h4 id="例顺序查找算法">例：顺序查找算法</h4>
<pre><code>(1) i = n - 1  
(2) while(i&gt;0; &amp;&amp; (A[i] != k))  
(3)      i--;    
(4)      return i;   
</code></pre>
<h4 id="分析-1">分析</h4>
<p>例 A = [9 , 10 , 32 , 78 , 50]<br>
查找成功：</p>
<ul>
<li>最坏的情况：A 中第一个元素为 K（例查找9）语句（3）的频度为 n 。</li>
<li>最好的情况：A 中最后一个元素为 K（例查找50）语句（3）的频度为 1 。</li>
</ul>
<p>查找失败<br>
所有元素都找不到（例查找5）查找次数为 n+1 次。
算法最坏时间复杂度为 O(n) 。</p>
<h3 id="算法的空间复杂度">算法的空间复杂度</h3>
<p>以存储单元个数刻画随问题规模增加的函数 f(n) ，存储空间量度记作：
S(n) = O(f(n))<br>
空间复杂度原理同时间复杂度，具体内容不在详细介绍。</p>
<h2 id="总结与提高">总结与提高</h2>
<ul>
<li>掌握数据的组织方式</li>
<li>掌握进行数据处理的基本技术</li>
<li>掌握算法设计分析的基本技能</li>
</ul>
<h3 id="数据结构的基本概念">数据结构的基本概念</h3>
<p>包括数据的逻辑结构，存储结构，和运算集合三部分。</p>
<h4 id="数据的逻辑结构">数据的逻辑结构</h4>
<ul>
<li>线性结构（1 : 1 , 线性表，栈，队列，字符串，数组，广义表等）</li>
<li>非线性结构（树 1：m , 图 m : n)</li>
</ul>
<h4 id="数据的存储结构">数据的存储结构</h4>
<ul>
<li>顺序存储（一组连续的配置单元）</li>
<li>非顺序存储（一组任意配置单元）</li>
</ul>
<h4 id="定义其上的运算集合">定义其上的运算集合</h4>
<p>掌握四类逻辑结构 ， 两类存储结构，掌握针对问题的数据组织方式。</p>
<h4 id="注意逻辑结构与存储结构的区别">注意逻辑结构与存储结构的区别</h4>
<ul>
<li>逻辑结构定义了数据元素之间的逻辑关系</li>
<li>存储结构是逻辑结构在计算机中的实现。</li>
</ul>
<p>一种逻辑结构可以采用不同存储方式存放在计算机中，但必须反映出要求的逻辑关系。</p>
<h3 id="算法与算法分析">算法与算法分析</h3>
<p>重点掌握算法的定义与特性,算法的正确性，算法的评价方法。</p>
</div>
                    <div class="post_footer">
                        
                        <div class="meta">
                            <div class="info">
                                <span class="field tags">
                                    <i class="ri-stack-line"></i>
                                    
                                    <a href="https://lenzan.github.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
                                    
                                </span>
                            </div>
                        </div>
                        
                    </div>
                </div>
                
                
            </div>
        </div>
    </div>
    <a id="back_to_top" href="#" class="back_to_top"><span>△</span></a>
    <footer class="footer">
    <div class="powered_by">
        <a href="https://varkai.com">Designed by VarKai,</a>
        <a href="http://www.gohugo.io/">Proudly published with Hugo</a>
    </div>

    <div class="footer_slogan">
        <span></span>
    </div>
</footer>
    <script src="https://lenzan.github.io/js/jquery-3.5.1.min.js"></script>
<link href="https://lenzan.github.io/css/fancybox.min.css" rel="stylesheet">
<script src="https://lenzan.github.io/js/fancybox.min.js"></script>
<script src="https://lenzan.github.io/js/zozo.js"></script>






</body>

</html>